package com.cn.algorithm02.class23;

/***
 * @author: hels
 * @description:  > 从左往右的尝试模型。
 * arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
 * 每个值都认为是一种面值，且认为张数是无限的。
 * 返回组成aim的最少货币数
 * 使用Integer.MAX_VALUE表示：无法组成。
 **/
public class C02_MinCoinsNoLimits {
    /** 暴力递归一 */
    public static int right1(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim <= 0) {
            return Integer.MAX_VALUE;
        }
        return process(arr, 0, aim);
    }

    private static int process(int[] arr, int index, int rest) {
//        if (rest < 0) {
//            return Integer.MAX_VALUE;
//        }
        int N = arr.length;
        if (index == N) {
            return rest == 0 ? 0 : Integer.MAX_VALUE;
        }
        int ans = Integer.MAX_VALUE;
        for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
            int next = process(arr, index +1, rest - zhang * arr[index]);
            if (next != Integer.MAX_VALUE) {
                ans = Math.min(ans, zhang + next);
            }
        }
        return ans;
    }

    /**
     * 暴力递归转动态规划
     * */
    public static int dp1(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim <= 0) {
            return Integer.MAX_VALUE;
        }

        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 0;
        for (int i = 1; i <= aim; i++) {
            dp[N][i] = Integer.MAX_VALUE;
        }

        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int ans = Integer.MAX_VALUE;
                for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
                    int next = dp[index +1][rest - zhang * arr[index]];
                    if (next != Integer.MAX_VALUE) {
                        ans = Math.min(ans, zhang + next);
                    }
                }
                dp[index][rest] = ans;
            }
        }
        return (int) dp[0][aim];
    }

    /**
     * 暴力递归转动态规划的优化版本
     * */
    public static int dp2(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim <= 0) {
            return Integer.MAX_VALUE;
        }

        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 0;
        for (int i = 1; i <= aim; i++) {
            dp[N][i] = Integer.MAX_VALUE;
        }

        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                dp[index][rest] = dp[index+1][rest];
                if (rest - arr[index] >= 0 && dp[index][rest - arr[index]] != Integer.MAX_VALUE) {
                    dp[index][rest] = Math.min(dp[index][rest], dp[index][rest - arr[index]] + 1);
                }
            }
        }
        return (int) dp[0][aim];
    }


    // 对数器：
    /** 创造数组, */
    public static int[] createArray(int maxValue, int maxLen) {
        int N = (int) (Math.random() * maxLen);
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            // 数组都是正数，有0会异常
            arr[i] = (int) (Math.random() * maxValue) + 1;
        }
        return arr;
    }


    public static void main(String[] args) {
        int maxValue = 20;
        int maxLen = 5;
        System.out.println("开始测试");
        for (int i = 0; i < 100; i++) {
            int[] arr = createArray(maxValue, maxLen);
            int aim = (int) (Math.random() * 20);
            int r = right1(arr, aim);
            int dp1 = dp1(arr, aim);
            int dp2 = dp2(arr, aim);
            if (r != dp1 || r!= dp2) {
                System.out.println("oops");
            }
        }
        System.out.println("结束测试");






//        int[] arr = {11, 10};
//        int aim = 51;
//        System.out.println(right1(arr, aim));
//        System.out.println(dp1(arr, aim));
//        System.out.println(dp2(arr, aim));
    }
}
